/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

        //思路就是存到第三个list中去
        ListNode* result = new ListNode(-1); //初始化
        ListNode* p = result;
        ListNode* p1 = l1;
        ListNode* p2 = l2;

        while(p1 != NULL && p2 != NULL)
        {
            if (p1->val <= p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;//p指针前进

        }

        if (p1 != NULL)
        {
            p->next = p1;

        }

        if (p2 != NULL)
        {
            p->next = p2;

        }

        return result->next;//引入-1的目的是减去很多不必要的操作
        


    }
};